/*
 * @lc app=leetcode.cn id=912 lang=javascript
 *
 * [912] 排序数组
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  quickSort(nums, 0, nums.length - 1);
  return nums;
};

var quickSort = function (nums, left, right) {
  if (left < right) {
    const index = partition(nums, left, right);
    quickSort(nums, left, index - 1);
    quickSort(nums, index + 1, right);
  }
};

var partition = function (nums, left, right) {
  const pivot = nums[left];

  while (left < right) {
    while (left < right && nums[right] >= pivot) {
      right--;
    }
    nums[left] = nums[right];
    while (left < right && nums[left] <= pivot) {
      left++;
    }
    nums[right] = nums[left];
  }
  nums[left] = pivot;
  return left;
};

// @lc code=end

// @after-stub-for-debug-begin
module.exports = sortArray;
// @after-stub-for-debug-end
